A CSP may be defined as a triplet P=<V, D, C>, involving a set of variables, V={v1, . . . , vn}, which take discrete values from their corresponding finite domains D={Dv1, . . . , Dvn}, and a set of constraints C={C1, . . . , Cm}. A constraint is an entity that restricts the values of one or more variables it relates to. For example, a constraint may be C1>C2+C3. As another example, a constraint may be (C1>C2) OR (C3<C4 AND C1=5). The constraint may utilize arithmetic operators, logic operators, or the like. In some exemplary embodiments, constraints may be presented as first order logic formulas over the variables. Additionally or alternatively, a constraint may be given as a set of possible assignments to one or more variables, such as (C1, C3)={(1,1),(2,2),(3,1)} which may indicate that the two variables C1 and C3 can be both assigned the value 1, both assigned the value 2, or C1 may be assigned the value 3 and C3 may be assigned the value 1.
A solution to the CSP problem is a single assignment of each variable such that the value of the variable belongs to its corresponding domain, and all the constraints are satisfied.
One of the known solving techniques for CSP is Maintain Arc Consistency (MAC). MAC is described in Dechter R., “Constraint Processing” (USA) 2003, which is hereby incorporated by reference in its entirety. In the MAC paradigm, CSP is solved by repeatedly performing two steps: (1) propagation and (2) instantiation.
The propagation step comprises restricting the domain of the variables to valid alternatives based on the constraints. Given a formula and a set of variables values, a propagator reduces the domain of the variables, removing values that cannot be combined with any set of values from the other variables to satisfy the constraints. Propagation may be performed until a fixed point is reached and no additional propagation may be performed.
The instantiation step is performed after the propagation step reaches a fixed point. A variable is chosen and instantiated to a single value or a subset values out of its corresponding domain. As the instantiation is not directly implied from the CSP, in some cases, some instantiations cause the CSP to become unsolveable, and may be backtracked.
The manner in which instantiation is performed has an impact on solver efficiency and the time it takes for the solution to be determined. Heuristics may be applied to reduce the number of backtracks and to gain performance speed-up. Many different types of heuristics are known in the literature, such as selecting the variables based on an order defined by a constraint network or based on a manual definition by a user.
CSP solvers may be utilized in variety of fields, such as for example verification, automatic scheduling, resource allocation algorithms, reactive planning, or the like. Generally, CSP solver solves an NP problem, or under some constraints an NP-complete problem.